package graphs;

import java.awt.Canvas;
import java.awt.Dimension;
import java.awt.Graphics;
import java.awt.Point;
import java.util.ArrayList;
import java.util.Collection;
import java.util.HashMap;
import java.util.ListIterator;

import javax.swing.JFrame;
import javax.swing.JPanel;
import javax.swing.text.html.HTMLDocument.Iterator;

import tester.Example;
import tester.TestMethod;
import tester.Tester;
import tester.cobertura.Instrument;
import lists.BinaryFunction;
import lists.MyArrayList;
import lists.UnaryFunction;

/**
 * <h1>Title : AdjacencyListGraph</h1>
 * <p>Description : Represents the <code>IGraph</code> as a <code>HashMap</code> 
 * of <code>Vertex</code>es which have a list of <code>Link</code>s, 
 * which are made up of a weight and a <code>vertex</code>.</p>
 * <p>This Method creates a circular data representation, but is quickly traversable, 
 * and mirrors the circularity of an actual graph</p> 
 * 
 * @author Adam Blackwell & Ryan Cassidy
 * @since February 22nd 2009
 * @version 1.4
 */
@Instrument @Example public class AdjacencyListGraph implements IGraph{
  /** <p>Number of vertices in the graph.</p> */
  private int                     verticesNumber;
  /** <p>Map used to map <code>vertex</code>es to their index used in the Adjacency List.</p> */
  private HashMap<String, Vertex> verticesMap;
  /** <p>Whether the <code>IGraph</code> is directed or not.</p> */
  private boolean DIRECTED = false;
  
  /** <p>Constructor : </p> */
  public AdjacencyListGraph() {
    this(new HashMap<String, Vertex>());
  }
  
  /** <p>Constructor : </p> 
   *  @param vertices */
  public AdjacencyListGraph(HashMap<String, Vertex> vertices) {
    this.verticesMap = vertices;
    this.verticesNumber = vertices.size();
  }

  // =================================================================
  // Builder Methods:
  // =================================================================
   
  /*
   * (non-Javadoc)
   * @see graphs.IGraph#addEdge(graphs.Vertex, graphs.Vertex, int)
   */
  public void addEdge(Vertex startVertex, Vertex destinationVertex,
                                int weight) {
    /* Checks if both nodes are in the ArrayList. */
    if (!verticesMap.containsKey(startVertex)) {
      this.addVertex(startVertex);
      this.addEdge(startVertex, destinationVertex, weight);
    } else if (!verticesMap.containsKey(destinationVertex)) {
      this.addVertex(destinationVertex);
      this.addEdge(startVertex, destinationVertex, weight);
    } else {
      Vertex st = verticesMap.get(startVertex.getName());
      st.addNeighbor(weight, destinationVertex);
      verticesMap.put(startVertex.getName(), st);
      Vertex end = verticesMap.get(destinationVertex.getName());
      end.addNeighbor(weight, startVertex);
      verticesMap.put(destinationVertex.getName(), end);
    }
  }
  
  /*
   * (non-Javadoc)
   * @see graphs.IGraph#addVertex(graphs.Vertex)
   */
  public void addVertex(Vertex vertex) {
    /* Adds the given <code>Vertex</code> with its extracted name into the <code>HashMap</code>. */
    this.verticesMap.put(vertex.getName(), vertex);
    /* Increments the number of vertexes */
    this.verticesNumber++;
  }
  
  /*
   * (non-Javadoc)
   * @see graphs.IGraph#removeEdge(graphs.Vertex, graphs.Vertex)
   */
  public void removeEdge(Vertex startVertex, Vertex destinationVertex) {
    /* Get the two <code>Vertex</code>es. */
    Vertex v1 = this.verticesMap.get(startVertex);
    Vertex v2 = this.verticesMap.get(destinationVertex);
    /* Remove the corresponding <code>Link</code>s. */
    v1.removeNeighbor(destinationVertex);
    v2.removeNeighbor(startVertex);
    /* Put them back in the <code>HashMap</code>. */
    this.verticesMap.put(v1.getName(), v1);
    this.verticesMap.put(v2.getName(), v2);
    verticesNumber--;
  }

  /* (non-Javadoc)
   * @see graphs.IGraph#removeVertex(graphs.Vertex)
   */
  public void removeVertex(Vertex vertex) {
    /* Calls remove on the <coed>HashMap</code> */
    this.verticesMap.remove(vertex.getName());
  }
  
  // =================================================================
  // Verifiers:
  // =================================================================
  
  /*
   * (non-Javadoc)
   * @see graphs.IGraph#vertexExist(graphs.Vertex)
   */
  public boolean vertexExist(Vertex vertex) {
    /* Checks if the key exists. */
    return verticesMap.containsKey(vertex.getName());
  }
  
  /*
   * (non-Javadoc)
   * @see graphs.IGraph#edgeExist(graphs.Vertex, graphs.Vertex)
   */
  public boolean edgeExist(Vertex startVertex,
                                     Vertex destinationVertex) {
    /* Checks both sides of the edge by checking if the two links exists. */
    return startVertex.hasNeighbor(destinationVertex)
           || destinationVertex.hasNeighbor(startVertex);
  }
  
  // =================================================================
  // Weight Calculators:
  // =================================================================
  
  /*
   * (non-Javadoc)
   * @see graphs.IGraph#getEdgeWeight(graphs.Vertex, graphs.Vertex)
   */
  public int getEdgeWeight(final Vertex startVertex,
                                     final Vertex destinationVertex) {
    /* Filters the "startVertex's" neighbors for <code>Link</code>s to the the
     * "destinationVertex"
     * Takes the first of the resulting list and gets the weight from
     * the <code>Link</code>.
     * This is absurd... */
    return this.verticesMap.get(startVertex.getName()).neighbors
    .filter(new UnaryFunction<Boolean, Link>() {
      public Boolean f(Link l) {
        return l.getDestinationVertex().equals(destinationVertex);
      }
    }).get(0).getWeight();
  }

  // =================================================================
  // Search Methods:
  // =================================================================
  
  /**
   * DepthFirstSearch : Search.
   * @param origin
   * @param dest
   * @return The path between the two given <code>Vertex</code>es. 
   * @throws Exception
   */
  public Path<Vertex> depthFirstSearch(String origin, String dest) throws Exception {
    /* Calls the helper with the correct base case arguments. */
    return this.depth(origin, dest, new Path<Vertex>());
  }

  /**
   * Depth : Helper.
   * @param current
   * @param dest
   * @param seen
   * @param path
   * @return The path between the two given <code>Vertex</code>es. 
   * @throws Exception
   */
  public Path<Vertex> depth(final String current, String dest, Path<Vertex> path) throws Exception {
    path.addVertex(this.verticesMap.get(current));
    /* Iterate through the list. */
    for (Link link : this.verticesMap.get(current).neighbors) {
      // System.out.println(path.toString());
      /* If the destination Vertex is not in the map. */
      if (this.allLinksVisited()) {
        throw new Exception("There is no path between the two given Vertexes.");
      /* If this is the final node, return the path with the end
       * vertex added to it. */
      } else if (link.getDestinationVertex().getName().equals(dest)) {
        path = path.addVertex(link.getDestinationVertex());
        break;
      /* Have we seen the current neighbor node (designated by
       * index) before? if so, skip it.  Otherwise set it to visited and recurse. */
      } else if (!link.isVisited()) {
        link.setVisited(true);
        /* This really isn't needed. */
        link.getDestinationVertex().setLinkVisited(current);
        this.depth(link.getDestinationVertex().getName(), dest, path);
      }
    }
    return path;
  }
  
  /**
   * BreadthFirstSearch : Search.
   * @param origin
   * @param dest
   * @return The path between the two given <code>Vertex</code>es. 
   * @throws Exception 
   */
  public Path<Vertex> breadthFirstSearch(String origin, String dest) throws Exception {
    /* Calls the helper with the correct base case arguments. */
    return this.breadth(verticesMap.get(origin), verticesMap.get(dest),
                    new MyArrayList<Vertex>(), new Path<Vertex>());
  }
  
  /**
   * Breadth : Helper.
   * @param origin
   * @param dest
   * @param queue
   * @param path
   * @return The path between the two given <code>Vertex</code>es. 
   * @throws Exception 
   */
  public Path<Vertex> breadth(Vertex current, Vertex dest,
                          MyArrayList<Vertex> queue, Path<Vertex> path) throws Exception {
    /* If you reach your destination return the accumulated path. */
    if (dest.getName().equals(current.getName()))
      return path.addVertex(current);
    /* For each neighbor that is not in queue or visited add the vertex to the queue,
     * and set visited to true, This could be expanded to do a priority queue. */
    for (Link l : current.neighbors) {
      if (!l.isVisited() && !queue.contains(l.getDestinationVertex())) {
        queue.add(l.getDestinationVertex());
        l.setVisited(true);
      }
    }
    /* Run the queue */
    for (Vertex v : queue) {
      /* If the current vertex is your destination return the accumulated path. */
      if (v.getName().equals(dest.getName()))
        return path.addVertex(v);
      /* Otherwise add their neighbors to the queue, and set those links to visited. */
      for (Link l1 : v.neighbors) {
        if (!l1.isVisited() && !queue.contains(l1.getDestinationVertex())) {
          queue.add(l1.getDestinationVertex());
          l1.setVisited(true);
        }
      }
    }
    /* If the destination Vertex is not in the map. */
    throw new Exception("There is no path between the two given Vertexes.");
  }

  
  /**
   * <p>AllLinksVisited : Have all the links been visited?</p>
   * @return The answer.
   */
  private boolean allLinksVisited() {
    boolean answer = true;
    /* Loop through the loops */
    for (Vertex v : this.verticesMap.values()) {
      for (Link l : v.neighbors)
      answer = answer && l.isVisited();
    }
    return answer;
  }

//  // =================================================================
//  // Draw Function:
//  // =================================================================
//  
//  /*
//   * (non-Javadoc)
//   * @see graphs.IPlottable#draw(java.awt.Canvas)
//   */
//  public void draw(Graphics g) {
//    // Draw
//    Collection<Vertex> i = this.verticesMap.values();
//    for(Vertex v : i) {
//      v.draw(g);
//      v.drawLinks(g);
//    }
//  }
  
  // =================================================================
  // Getters:
  // =================================================================
  
  /*
   * (non-Javadoc)
   * @see graphs.IGraph#getAdjacentVertices(graphs.Vertex)
   */
   public ListIterator<Vertex> getAdjacentVertices(Vertex vertex) {
    /* Maps The created UnaryFunction to the Link list. */
    return verticesMap.get(vertex.getName()).neighbors
    .map(new UnaryFunction<Vertex, Link>() {
       public Vertex f(Link l) {
        /* Returns the Vertex out of the Link. */
        return l.getDestinationVertex();
      }
    }).listIterator();
  }
   
  /*
   * (non-Javadoc)
   * @see graphs.IGraph#getAdjacentVertices(graphs.Vertex)
   */
   public ListIterator<String> getAdjacentVertexNames(Vertex vertex) {
    /* Maps The created UnaryFunction to the Link list. */
    return verticesMap.get(vertex.getName()).neighbors
    .map(new UnaryFunction<String, Link>() {
       public String f(Link l) {
        /* Returns the Vertex out of the Link. */
        return l.getDestinationVertex().getName();
      }
    }).listIterator();
  }

  /*
   * (non-Javadoc)
   * @see graphs.IGraph#getVerticesNumber()
   */
  public int getVerticesNumber() {
    /* Returns the number of <code>Vertex</code>es. */
    return this.verticesNumber;
  }
  
  /* (non-Javadoc)
   * @see graphs.IGraph#getVerticesMap()
   */
  public HashMap<String, Vertex> getVerticesMap() {
    /* Returns the <code>HasMap</code> of <code>Vertex</code>es. */
    return verticesMap;
  }
  
  /*
   * (non-Javadoc)
   * @see graphs.IGraph#getDirected()
   */
  public boolean getDirected() {
    /* Returns the <code>DIRECTED</code> field */
    return this.DIRECTED;
  }

  // =================================================================
  // Main Method :
  // =================================================================
  /**
   * <p>
   * Main Method. To Play with.
   * </p>
   */
  public static void main(String[] args) {
    AdjacencyListGraph a = new AdjacencyListGraph();
    a.init();
    // GraphPanel p = new GraphPanel(a);
    // p.setPreferredSize(new Dimension(500, 400));
    // JFrame j = new JFrame();
    // j.getContentPane().add(p);
    // j.pack();
    // j.setVisible(true);
    /* Temporary testing. */
    System.out.println("Depth");
    try {
      System.out.println(a.depthFirstSearch("Boston", "Portland").toString());
    } catch (Exception e) {
      /* Return the message to the terminal */
      System.out.println(e.getMessage());
    }
    a.init();
    try {
      System.out.println(a.depthFirstSearch("Boston", "Anchorage").toString());
    } catch (Exception e) {
      /* Return the message to the terminal */
      System.out.println(e.getMessage());
    }
    a.init();
    try {
      System.out.println(a.depthFirstSearch("Anchorage", "Boston").toString());
    } catch (Exception e) {
      /* Return the message to the terminal */
      System.out.println(e.getMessage());
    }
    a.init();
    System.out.println("Breadth");
    try {
      System.out.println(a.breadthFirstSearch("Anchorage", "Boston").toString());
    } catch (Exception e) {
      /* Return the message to the terminal */
      System.out.println(e.getMessage());
    }
  }

  // =================================================================
  // Tests:
  // =================================================================
 
  private City c1, c2, c3, c4 = new City();
  private Link l1, l2, l3, l4 = new Link();
  ArrayList<Link> c1neigh, c2neigh;
  
  /**
   * <p> Initializes Examples. </p> 
   */
  public void init() {
    /* Inits : */
    c1 = new City("Boston", new MyArrayList<Link>(), "MA", new Point(200, 350));
    c2 = new City("Portland", new MyArrayList<Link>(), "ME", new Point(300, 150));
    c3 = new City("Concord", new MyArrayList<Link>(), "NH", new Point(150, 200));
    c4 = new City("Anchorage", new MyArrayList<Link>(), "AK", new Point(30, 20));

    l1 = new Link(3, c1, false);
    l2 = new Link(3, c2, false);
    l3 = new Link(3, c3, false);
    l4 = new Link(3, c4, false);
    
    c2.neighbors.add(l1);
    c1.neighbors.add(l2);
    
    c2.neighbors.add(l3);
    c3.neighbors.add(l2);
    
    c2.neighbors.add(l4);
    c4.neighbors.add(l2);
    
    c1.neighbors.add(l2);
    c2.neighbors.add(l1);

    c1.neighbors.add(l3);
    c3.neighbors.add(l1);
    
    this.addVertex(c1);
    this.addVertex(c2);
    this.addVertex(c3);
    this.addVertex(c4);
    
    /* Answers */
    
    c1neigh = new ArrayList<Link>();
    c1neigh.add(l2);
    c1neigh.add(l3);
    c2neigh = new ArrayList<Link>();
    c1neigh.add(l1);
    c1neigh.add(l3);
    
  }

  // Test Methods
  @TestMethod
  public void testGetAjacentVertices(Tester t){
    AdjacencyListGraph a = new AdjacencyListGraph();
    a.init();
    t.checkExpect(a.getAdjacentVertices(a.c1), a.c1neigh);
    t.checkExpect(a.getAdjacentVertices(a.c2), a.c2neigh);
  }

  @TestMethod
  public void testAddRemoveEdge(Tester t){
    AdjacencyListGraph a = new AdjacencyListGraph();
    a.init();
    a.removeEdge(a.c1, a.c2);
    t.checkExpect(a.verticesMap.get(a.c1.getName()).neighbors.contains(a.l2), false);
    a.addEdge(a.c2, a.c3, 23);
    t.checkExpect(a.verticesMap.get(a.c2.getName()).neighbors.contains(a.l3), true);
  }

  @TestMethod
  public void testAddRemoveVertex(Tester t){
    AdjacencyListGraph a = new AdjacencyListGraph();
    a.init();
    a.removeVertex(a.c1);
    t.checkExpect(a.verticesMap.containsKey(a.c1.getName()), false);
    a.addVertex(a.c1);
    t.checkExpect(a.verticesMap.containsKey(a.c1.getName()), true);
  }

  @TestMethod
  public void testVertexExist(Tester t){
    AdjacencyListGraph a = new AdjacencyListGraph();
    a.init();
    a.removeVertex(a.c1);
    t.checkExpect(a.vertexExist(a.c1), false);
    a.addVertex(a.c1);
    t.checkExpect(a.vertexExist(a.c1), true);
  }
  
  @TestMethod
  public void testEdgeExist(Tester t){
    AdjacencyListGraph a = new AdjacencyListGraph();
    a.init();
    t.checkExpect(a.edgeExist(a.c1, a.c2), true);
    t.checkExpect(a.edgeExist(a.c2, a.c3), true);
    t.checkExpect(a.edgeExist(a.c3, a.c1), true);
    t.checkExpect(a.edgeExist(a.c1, a.c3), true);
  }

  @TestMethod
  public void testGetEdgeWeight(Tester t){
    AdjacencyListGraph a = new AdjacencyListGraph();
    a.init();
    t.checkExpect(a.getEdgeWeight(a.c1, a.c2), 3);
    t.checkExpect(a.getEdgeWeight(a.c2, a.c3), 3);
    t.checkExpect(a.getEdgeWeight(a.c1, a.c3), 3);
  }
  
  @TestMethod
  public void testDepthFirstSearch(Tester t){
    AdjacencyListGraph a = new AdjacencyListGraph();
    a.init();
    MyArrayList<Vertex> testpathlist = new MyArrayList<Vertex>();
    testpathlist.add(c1);
    testpathlist.add(c2);
    Path<Vertex> testpath = new Path<Vertex>(testpathlist);
  }
  
  @TestMethod
  public void testDepth(Tester t){
    AdjacencyListGraph a = new AdjacencyListGraph();
    a.init();
    MyArrayList<Vertex> testpathlist = new MyArrayList<Vertex>();
    testpathlist.add(c1);
    testpathlist.add(c2);
    Path<Vertex> testpath = new Path<Vertex>(testpathlist);
  }
  
  @TestMethod
  public void testBreadthFirstSearch(Tester t){
    AdjacencyListGraph a = new AdjacencyListGraph();
    a.init();
    MyArrayList<Vertex> testpathlist = new MyArrayList<Vertex>();
    testpathlist.add(c1);
    testpathlist.add(c2);
    Path<Vertex> testpath = new Path<Vertex>(testpathlist);
  }
  
  @TestMethod
  public void testBreadth(Tester t){
    AdjacencyListGraph a = new AdjacencyListGraph();
    a.init();
    MyArrayList<Vertex> testpathlist = new MyArrayList<Vertex>();
    testpathlist.add(c1);
    testpathlist.add(c2);
    Path<Vertex> testpath = new Path<Vertex>(testpathlist);
  }
  
//  @TestMethod
//  public void testDraw(Tester t){
//    AdjacencyListGraph a = new AdjacencyListGraph();
//    a.init();
//    GraphPanel p = new GraphPanel(a);
//    p.setPreferredSize(new Dimension(500, 400));
//    // TODO SO what should I test?
//  }
}